package leaderus.study;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;

public class PersonLimitMNByRadisSort {
	public static void radixSort(int[] data, int radix, int d) {  
        // 缓存数组  
        int[] tmp = new int[data.length];  
        // buckets用于记录待排序元素的信息  
        // buckets数组定义了max-min个桶  
        int[] buckets = new int[radix];  
        int t=(radix-1);
        for (int i = 0, rate = 1; i < d; i++) {  
            // 重置count数组，开始统计下一个关键字  
            Arrays.fill(buckets, 0);  
            // 将data中的元素完全复制到tmp数组中  
            System.arraycopy(data, 0, tmp, 0, data.length);  
  
            // 计算每个待排序数据的子关键字  
            int div=(int)(Math.log(rate)/Math.log(2));
            for (int j = 0; j < data.length; j++) {  
                int subKey = (tmp[j] >> div) & t;  
                buckets[subKey]++;  
            }  
  
            for (int j = 1; j < radix; j++) {  
                buckets[j] = buckets[j] + buckets[j - 1];  
            }  
  
            // 按子关键字对指定的数据进行排序  
            for (int m = data.length - 1; m >= 0; m--) {  
                int subKey = (tmp[m] >> div) & t;  
                data[--buckets[subKey]] = tmp[m];  
            }  
            rate*=radix;
        }  
  
    } 
    
    public int[] loadSortArray(String fileName){
		File personFile=new File(fileName);
		int[] sortArray=new int[1000000];
		if (personFile.exists() && personFile.isFile()) {
			try {
				InputStreamReader read = new InputStreamReader(new FileInputStream(personFile));
				BufferedReader bufferedReader = new BufferedReader(read);
				String infoLine;
				String[] infos;
				int i=0;
				while ((infoLine = bufferedReader.readLine()) != null) {
					infos = infoLine.split(",");
					sortArray[i]=Integer.valueOf(infos[0]);
					i++;
				}
			} catch (Exception e) {
				e.printStackTrace();
			}
		}else{
			System.out.println("找不到指定文件！");
		}
		return sortArray;
	}

    public static void main(String[] args) {
    	String tableFile=GenRandomersonDBFile.path + "//"+ GenRandomersonDBFile.fileName;
    	PersonLimitMNByRadisSort personLimitMNByRadisSort = new PersonLimitMNByRadisSort();
		int[] intArray=personLimitMNByRadisSort.loadSortArray(tableFile);
		long startTime=System.currentTimeMillis();
		personLimitMNByRadisSort.radixSort(intArray,2048,3);
		System.out.println("基数排序耗时："+(System.currentTimeMillis()-startTime)+"ms");
		for(int i=900000;i<900100;i++){
			System.out.println(intArray[i]);
		}
    }

}
